package com.axzh.interview.algorithm;

/**
 * 最长公共子序列<br>
 * 最长公共子串
 * @author Administrator
 *
 */
public class LcsProblem {

	public static void main(String[] args) {
		String a = "ACCGGTCGAGTGCGCGGAAGCCGGCCGAA";
		String b = "GTCGTTCGGAATGCCGTTGCTCTGTAAA";
		LcsProblem.longestCommonSubsequence(a, b);
		String c = "bcdaaaaaaaa";
		String d = "bcterabcd";
		LcsProblem.longestCommonSubstring(c, d);
	}
	
	/**
	 * 最长公共子序列
	 * @param a
	 * @param b
	 */
	public static void longestCommonSubsequence(String a, String b) {
		String[][] result = new String[a.length()+1][b.length()+1];
		char[] ch1 = a.toCharArray();
		char[] ch2 = b.toCharArray();
		for(int i=0;i<a.length()+1;i++) {
			result[i][0]="";
		}
		for(int j=0;j<b.length()+1;j++) {
			result[0][j]="";
		}
		for(int i=1;i<a.length()+1;i++) {
			for(int j=1;j<b.length()+1;j++) {
				if(ch1[i-1]==ch2[j-1]) {
					result[i][j]=result[i-1][j-1]+ch1[i-1];
				} else {
					result[i][j]=result[i-1][j].length()>result[i][j-1].length()?result[i-1][j]:result[i][j-1];
				}
			}
		}
		/*for(int i=0;i<a.length()+1;i++) {
			for(int j=0;j<b.length()+1;j++) {
				System.out.print(result[i][j]+"\t");
			}
			System.out.println();
		}*/
		System.out.println(result[a.length()][b.length()]);
	}
	
	/**
	 * 最长公共子串
	 * @param a
	 * @param b
	 */
	public static void longestCommonSubstring(String a, String b) {
		int[][] dp_table = new int[a.length()+1][b.length()+1];
		char[] ch1 = a.toCharArray();
		char[] ch2 = b.toCharArray();
		for(int i=0;i<a.length()+1;i++) {
			dp_table[i][0]=0;
		}
		for(int j=0;j<b.length()+1;j++) {
			dp_table[0][j]=0;
		}
		int max=0,x=0,y=0;
		for(int i=1;i<a.length()+1;i++) {
			for(int j=1;j<b.length()+1;j++) {
				if(ch1[i-1]==ch2[j-1]) {
					dp_table[i][j]=dp_table[i-1][j-1]+1;
				} else {
					dp_table[i][j]=0;
				}
				if(dp_table[i][j]>max) {
					max = dp_table[i][j];
					x= i-1;
					y=j-1;
				}
			}
		}
		char[] result = new char[max];
		//StringBuilder sb = new StringBuilder();
		while(x>=0 && y>=0) {
			if(ch1[x]==ch2[y]) {
				result[--max]=ch1[x];
				x--;
				y--;
			} else {
				break;
			}
		}
		System.out.println(new String(result));
	}

}
